Segment Tree
问题描述
首先，回到树状数组的问题：
给定$n$个数字，有两种频繁的操作需要处理：
- 求$\sum_{k = i}^j A_k$；
- 对某个$A_i$数据进行增减操作。
对于这种情况，使用树状数组肯定是十分方便的，而且编程十分的简单。
但是如果题目的要求更加的灵活，树状数组在很多的情况下是不适和的。(或者更准确的说，对设计技巧要求更高)
现在需要有一个支持区间更新、区间查询等等操作的数据结构，并且要保证每个操作基本可以在$O(\lg n)$的时间完成。
于是我们引入了线段树的数据结构。通过将整体区间进行分割，由叶节点管理最小的分割单元，其他节点以类似$2^k$的形式逐层进行管理。
算法介绍
问题建模
类似区间树，在各个节点保存一条线段（数组中的一段子数组），可以高效解决连续区间的动态查询问题，由于二叉结构的特性。
线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是$[a, b]$，那么$mid = \frac{a+b}{2}$，左儿子的区间是$[a, mid]$，右儿子的区间是$[mid + 1, b]$。
于是，当我们需要查询一段数据的时候，只需要查询对应的大区间即可，而不用一个点一个点的查询。如下图所示：
如果我们需要查询$[0, 3]$上的最值，我们不需要查找$3$次找到结果，只要按照$2^k$的顺序，依次查找$[0, 2]$和$[3, 3]$即可。
对于修改的问题，处理比较特殊。理论上，我们必须要将每个点的值进行修改以后，再重新更新它的所有的祖先节点。但是这样以来，复杂度就是$O(n\lg n)$了，不符合我们的要求。
考虑一种方法，如果我们几乎每次都访问一个长区间，是不是最小的叶子节点上的值就不重要了呢？换句话说，如果操作都是基于长区间的，我们可以把这些区间当作是一个叶节点来进行操作。只要每次都修改这个区间的数值就好。
但是这样一来，访问单点就会出问题，所以我们可以使用一个“$lazy$的思想”：如果访问的区间刚好在包括了这个点代表的整个区间，我们就不需要向下继续的修改。只要使用一个$lazy$的标记，表示这个区间下面的点，还没有被修改，如果希望访问，请先修改后再访问；如果不需要继续访问它的孩子，修改的操作仍然可以延后。
求解方法
线段树的代码针对不同问题有多种写法，但是基本的思想都是一致的。
先引入$pushUp$和$pushDown$两种思想，即根据子节点修改父节点和根据父节点$lazy$的标记修改子节点。
|
|
|
|
下面我们可以使用递归的方法进行建树：
|
|
对于修改操作，需要灵活的运用$lazy$的思想，下面的代码仅仅给出例子，但是具体何时进行修改，需要针对具体的题目来定。
|
|
查询比较简单，注意如果要求查询的区间比较小，需要将现在的区间进行划分以后才能查询的话，我们必须要在下一次递归查询之前，通过$pushDown$的操作，将$lazy$标记向下传播，否则会查询出错。
|
|
解题报告
Poj 2777 Count Color
问题描述
Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.
There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:
- “C A B C” Color the board from segment A to segment B with color C.
- “P A B” Output the number of different colors painted between segment A and segment B (including).
In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.
Input
First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains “C A B C” or “P A B” (here A, B, C are integers, and A may be larger than B) as an operation defined previously.
Output
Ouput results of the output operation in order, each line contains a number.
算法设计
这道题目很明显是通过线段树进行区间的查询修改，所以我们可以对于每一个节点，除了叶节点以外，维护一个30个元素的数组，记录自己的孩子节点里面都哪些颜色。
但是，虽然Poj上给的空间比较多，但是还是显得比较笨拙，所以我们可以使用位操作。因为一个$int$刚好是$4$字节，即$32$位，所以只要一个$int$型的数就可以记录下所有的颜色。
其余的操作就是标准的线段树的写法。注意，因为区间修改是把区间里面的点全部修改为一种颜色，所以在进行$pushDown$的操作的时候，只需要让子节点和父节点的颜色相同，就可以了。
程序代码
|
|
性能分析
之前已经分析过，线段树的操作复杂度是$O(\lg n)$的，所以对于这道题目，时间的复杂度就是$O(n\lg n)$。
编程技术技巧
此题是第一道线段树的题目，主要有两个位操作值得一提：
访问子节点
因为子节点一定是父节点编号的$2$倍，所以如果线段树的储存从$1$开始，我们可以看出，通过一个位移的操作刚好可以访问到左节点：
left = root<<1。对于右节点，理论上就是左节点$+1$，但是考虑到右移以后，最低位刚好为$0$，所以直接通过一个或运算，就可以加一：right = (root<<1)|1。颜色的储存
这里的方法比较巧妙，通过每一位表示一个颜色，对最后的结果进行存储。其中，还可以比较方便的使用位操作的或进行颜色的加和。
Poj 1470 Closest Common Ancestors
问题描述
Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.
The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i‘s silhouette has a base that spans locations Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.
Input
Line 1: A single integer: N
Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: Ai, Bi, and HiOutput
Line 1: The total area, in square units, of the silhouettes formed by all N buildings
算法设计
如图，这道题目需要求出由建筑物组成的剪影，需要查询整个区间的剪影面积。
乍一看和线段树没有明显的关系，但是仔细分析：题目只涉及到面积的求解，所以不需要区分某一个具体的建筑。我们可以把每一段的高度通过线段树储存，最后每个区间进行分别的计算，最后求出总和。
但是此题的横坐标范围很大，如果直接使用线段树进行储存，空间开销过大。(注：根据二叉树的性质，叶节点和其余节点的个数相等)，所以理论上空间的开销是$2$倍的$n$，考虑到不是一个满的二叉树，空间开销有可能达到$4$倍的$n$节点。
所以，需要对于空间进行压缩，这里使用的还是和之前并查集的那个章节一样的$hash$映射的方法，通过一次$hash$的$map$操作，大大节省了空间。但是需要注意的是，这里的计算面积的时候，仍然需要将原先的数据映射回来进行计算。
程序代码
|
|
性能分析
和之前一样，$n$次的插入操作使得时间复杂度变成$O(n\lg n)$，对于$map$的映射而言，同样也是$O(n\lg n)$的复杂度，所以总共的时间复杂度就是$O(n)$。对于空间来说，因为使用$hash$的方法，所以只和输入的大楼个数有关，复杂度是$O(n)$。
编程技术技巧
这道题目仍然使用了$hash$映射的方式来节省空间，但是值得注意的是，此时线段树的空间大小不可以仅仅只是$n$，因为线段树在访问的时候，对于底层的节点仍然使用了递归的方法进行访问，所以如果空间没有开辟的足够大，有可能出现访问越界等等错误的情况。一般来说，$3$倍的空间是够用的。
Poj 3667 Hotel
问题描述
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
Line 1: Two space-separated integers: N and M
Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di
Output
Lines 1…..: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
算法设计
Hotel题目比较复杂，主要体现在每个节点需要保存的数据比较多，每一次的$pushDown$和$pushUp$的操作过程稍微繁琐。
因为题目需要求出最大的连续区间满足房屋分配的条件，所以我们需要使用$3$个数据分别保存区间中最大的连续房间，从左边开始的连续房间，从右边向左开始的连续房间。为什么要保存这种数据呢？因为在进行区间和合并的时候，有可能新的大区间内，是由左节点的右边区间和右节点的左边区间合并拼凑起来的。所以需要进行一个比较。
剩余的操作和前面的题目基本一致，这里不再进行赘述。
程序代码
|
|
性能分析
题目虽然每一次的操作相对于前面复杂了不少，但是由于操作都是$O(1)$的比较操作，所以印象不大，仍然是$O(n\lg n)$的复杂度。
编程技术技巧
此题展现了线段树结构的强大之处，其节点内部可以储存很多的信息，在$pushDown$和$pushUp$的操作中，我们需要保证信息的正确性，使得线段树发挥很大的威力。